For the course Multi Agent Systems (year 2011-2012) we developed an application in which 4 players play the Dutch card game Zwarte Pieten, which is equal to the English card game Old Maid. In the application we keep track of the logic and knowledge the agents have about the game (and cards in the game).
This website explains the game and our project. Feel free to browse around.
Frank Doesburg, Koen Brinks and Joost Timmerman
The card game Old Maid can be played by two or more players. From a standard 52 card pack, remove one queen and all cards with a value lower than 7. This leaves 31 cards. Deal and play are clockwise.
The dealer deals out all the cards to the players (generally some will have one more card than others - this does not matter). The players all look at their cards and discard any pairs they have (a pair is two cards of equal rank, such as two sevens or two kings). Discarded pairs will be put face up on the table.
The player next to the dealer begins. The player on the right of her offers her cards spread face down to the player who's turn it is. That player selects a card from the hand without seeing it, and adds it to her hand. If it forms a pair with another card in her hand she discards the pair. The player who just took a card then offers her hand to the next player to her left, and so on.
If you've discarded all your cards you are safe - the turn passes to the next player and you take no further part. Eventually all the cards will have been discarded except one queen and the holder of this queen loses.
In our project we coded the dutch version of the game with 4 agents/players. The dutch variant of Old Maid is called Zwarte Pieten. The only difference with the English version is that a jack (but not the jack of spades) is removed from the game instead of a queen, and that the holder of the jack of spades is the one who loses the game (the jack of spades can not be discarded during the game, even if it forms a pair).
When playing the game, agents in the game have logic knowledge about the whereabouts of cards. After dealing the cards, all agents know what cards they have themselves. Besides that, they also consider it possible that all cards that they do not have themselves, but are known to be in the game, are in possession of any of the other players. When a pair of cards is discarded to the table, every agent then knows the whereabouts of this pair of cards. They also know that all other agents know they know this. This can be repeated into infinity, thus creating common knowledge about these cards. This also is automatically the case when there are only two players left in the game, because the cards on the table and in their own hand are known, thus enabling the agents to determine what cards the other player has in her hand. They both know this from eachother, thus again there is common knowledge about the cards.
Logical knowledge is constantly changing during the game, especially for the agent who draws a card and the agent from who a card is drawn. The agent from who a card is drawn knows that the agent who draws a card then has that card in possession. She then doesn't consider it possible any more that the other agents have the card. The drawing agent knows that the agent from who she just drew the card knows that she has the card in possesion. In the next turn, it is possible that the agent who then draws a card, draws the previous card in question. Therefore, the certain knowledge of the previous player becomes 'considers it possible' knowledge. When there are still 4 players left, the agent for which this knowledge changes still does not consider it possible that the fourth agent has the card, because he didn't participate in the exchanges discussed.
In our implementation, we conform to the axioms in axiom systems S5EC* and KD45*, and assume the agents are perfect logicians.
We explicitly modelled the logic in our program using the following propositions:
Ki [card] j
meaning: Agent i knows that [card] is at possition j.
Mi [card] j
meaning: Agent i considers it possible that [card] is at possition j.
C [card] j
meaning: It is common knowledge that [card] is at possition j (For confeniance, in our code, C was modelled as Ci (with i for all players in the game)).
In our axiom system, we don't use beliefs because these don't allow us to model multiple logical sentences which are contradicting. Therefore, we use M-logic adapted from the system Dual-KD45*. By using M-logic we can model -using seperate sentences- that a card is at multiple locations at once; something that is impossible when using Beliefs.
Implicitly, the logic in our program also holds that when an agent knows 'x', he knows that he knows 'x' (axiom A4*). The same is true for facts you don't know (according to axiom A5*).
*: see 'Epistemic Logic for AI and Computer Science (by J.-J. Ch. Meyer and W. van der Hoek.)
ISBN: 978-0-521-60280-8.
Example 1:
We're looking at a game with four agents (agent 1 to 4). It is agent 3's turn, and she draws a random card from agent 2, let's say that this card is the ace of hearts and that this card does not form a pair with the cards agent 3 already has. The 'newly' formed knowledge of agent 2 and 3 then is as follows:
- K3 'ace of hearts' 3 (agent 3 knows that he has the ace of hearts).
- K3 K2 'ace of hearts' 3 (agent 3 knows agent 2 knows he has te ace of hearts).
- K2 'ace of hearts' 3 (agent 2 knows agent 3 has the ace of hearts).
- K2 K3 K2 'ace of hearts' 3 (agent 2 knows that agent 3 knows that agent 2 knows that agent 3 has the ace of hearts).
- Both agent 2 and 3 now no longer consider it possible (M-knowledge) that other agents have the ace of hearts.
In the next turn, agent 4 draws a random card from agent 3. The previously 'new' knowledge of agent 2 and 3 now changes to the following:
- K3 'ace of hearts' x (agent 3 knows that the ace of hearts is at location 'x' (with 'x' being 3 or 4 (if agent 4 now has the ace of hearts, agent 3 will produce more new logic (similar to step 1 in this example).
- K3 M2 'ace of hearts' 3 (agent 3 knows agent 2 thinks it is possible he has te ace of hearts).
- M2 'ace of hearts' 3 (agent 2 holds it possible that agent 3 has the ace of hearts).
- K2 K3 M2 'ace of hearts' 3 (agent 2 knows that agent 3 knows that agent 2 holds it possible that agent 3 has the ace of hearts).
- Also, agent 2 now considers it possible that the ace of hearts is in possession of agent 4 (M2 'ace of hearts' 4).
In the next turn, all knowledge agent 2 has about this card will change to M-knowledge (because then it is possible that player 3, 4 or 1 has the card in question), therefore, agent 3 now discards her knowlege about the knowledge of agent 2.
It is good to know that in the example above we only look at the newly created knowledge of the two agents about one single card. In reality, we keep track of all cards and the logical knowledge of all agents. Even when we look only at the logical knowledge of the single card, this card can be re-drawn by the following agent in the next turn, or it can form a pair and be discarded to the table (becoming available for all agents to change their knowledge about it).
Example 2:
We're looking at a game with 3 agents remaining (agent 1 to 3. Agent 4 has no cards left, thus she has left the game).
-Let's say agent 1 has only one card left, and it is agents 2's turn to draw a card from agent 1. When she does, agent 1 leaves the game because she has no cards left. The game now continues between agent 2 and 3, but there's is a major change in the logical knowledge. Because the two remaining agents now know for sure what cards they have in their hands and what cards are on the table, they can derive what cards are in the game besides the cards in these two locations. These 'missing' cards must then be in the hand of the other player. Because both agents know this of eachother, and because they know the other player knows that they know (this holds into infinity) we can state that knowledge of all the cards now is common.
Discussion:
We have created a working model of the game Zwarte Pieten. While following the progress of the game, one can also follow the development of the knowledge of the players in the game. We tried to do this as complete as possible without including information that is not necessary for following the game. For example: when a fact about a card has become common knowledge , it is not necessary to also model that every agent seperately knows that fact. One can deduct this knowledge using the rules of our axiom system. This way, when using the model, one can keep track of all relevant knowledge without cluttering the presented knowledge.
A limitation of this game is that the players have little to no influence on how they perform in the game, or how they can influence the game. Although players have knowledge about cards in the game, they cannot use this knowledge. Cards are distributed and then drawn at random. Each player performs actions according to the strict rules of the game. The game has no options for players to implement strategies in order to perform better.
If you whish to download or run our final application on your own computer we offer a jar-instance of our implementation. You can download it by clicking the box below, or by following this link.
Note that you need to have the Java JRE installed for running jar-files.